{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Fruit Into Baskets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: totalFruit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #水果成篮"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 <code>fruits</code> 表示，其中 <code>fruits[i]</code> 是第 <code>i</code> 棵树上的水果 <strong>种类</strong> 。</p>\n",
    "\n",
    "<p>你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你只有 <strong>两个</strong> 篮子，并且每个篮子只能装 <strong>单一类型</strong> 的水果。每个篮子能够装的水果总量没有限制。</li>\n",
    "\t<li>你可以选择任意一棵树开始采摘，你必须从 <strong>每棵</strong> 树（包括开始采摘的树）上 <strong>恰好摘一个水果</strong> 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。</li>\n",
    "\t<li>一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数数组 <code>fruits</code> ，返回你可以收集的水果的 <strong>最大</strong> 数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>fruits = [<em><strong>1,2,1</strong></em>]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>可以采摘全部 3 棵树。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>fruits = [0,<em><strong>1,2,2</strong></em>]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>可以采摘 [1,2,2] 这三棵树。\n",
    "如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>fruits = [1,<em><strong>2,3,2,2</strong></em>]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>可以采摘 [2,3,2,2] 这四棵树。\n",
    "如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>fruits = [3,3,3,<em><strong>1,2,1,1,2</strong></em>,3,3,4]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>可以采摘 [1,2,1,1,2] 这五棵树。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= fruits.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= fruits[i] &lt; fruits.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [fruit-into-baskets](https://leetcode.cn/problems/fruit-into-baskets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [fruit-into-baskets](https://leetcode.cn/problems/fruit-into-baskets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,1]', '[0,1,2,2]', '[1,2,3,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# [3,3,3,1,2,1,1,2,3,3,4]\n",
    "#  |     |\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree: List[int]) -> int:\n",
    "        max_count = 0\n",
    "        if len(tree) <= 2:\n",
    "            return len(tree)\n",
    "        fruit_A = tree[0]\n",
    "        fruit_B = tree[1]\n",
    "        count_B = 2 if fruit_A == fruit_B else 1\n",
    "        curr_count = 2\n",
    "        for fruit in tree[2:]:\n",
    "            if fruit == fruit_B:\n",
    "                curr_count += 1\n",
    "                count_B += 1\n",
    "            elif fruit == fruit_A:\n",
    "                curr_count += 1\n",
    "                count_B = 1\n",
    "                fruit_A = fruit_B\n",
    "                fruit_B = fruit\n",
    "            else:\n",
    "                max_count = max(curr_count, max_count)\n",
    "                curr_count = count_B + 1\n",
    "                count_B = 1\n",
    "                fruit_A = fruit_B\n",
    "                fruit_B = fruit\n",
    "                \n",
    "        return max(max_count, curr_count)\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "#         slow\n",
    "        # maxFruit = 0\n",
    "        # curr_tree = 0\n",
    "        # len_tree = len(tree)\n",
    "        # if len_tree <= 2:\n",
    "        #     return len_tree\n",
    "        # for i in range(1, len_tree):\n",
    "        #     braket = tree[curr_tree:i+1]\n",
    "        #     if len(set(braket)) <= 2:\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         maxFruit = max(maxFruit, len(braket) - 1)\n",
    "        #         if len_tree - i < maxFruit:\n",
    "        #             return maxFruit\n",
    "        #         while len(set(braket)) > 2:\n",
    "        #             curr_tree += 1\n",
    "        #             braket = tree[curr_tree:i+1]\n",
    "        #         if len_tree - curr_tree < maxFruit:\n",
    "        #             return maxFruit\n",
    "        # maxFruit = max(maxFruit, len(braket))\n",
    "        # return maxFruit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree):\n",
    "        \"\"\"\n",
    "        :type tree: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # one pass\n",
    "        # if not tree:\n",
    "        #     return 0\n",
    "        # n = len(tree)\n",
    "        # p1 = 0\n",
    "        # p2 = 0\n",
    "        # p3 = 0\n",
    "        # l1 = 0\n",
    "        # l2 = 0\n",
    "        # max_cur = 0\n",
    "        # while p3 < n:\n",
    "        #     if tree[p1] == tree[p2]:\n",
    "        #         p2 += 1\n",
    "        #         p3 += 1\n",
    "        #     elif tree[p1]== tree[p3]:\n",
    "        #         if tree[p3-1] != tree[p3]:\n",
    "        #             l1 = p3\n",
    "        #         p3 += 1\n",
    "        #     elif tree[p2] == tree[p3]:\n",
    "        #         if tree[p3-1] != tree[p3]:\n",
    "        #             l2 = p3\n",
    "        #         p3 += 1\n",
    "        #     else:\n",
    "        #         if p3 - p1 > max_cur:\n",
    "        #             max_cur = p3 - p1\n",
    "        #         p1 = max(l1, l2, p2)\n",
    "        #         p2 = p3\n",
    "        # return max(max_cur, p3 - p1)\n",
    "        \n",
    "        \n",
    "        # two pass\n",
    "#         if len(tree) < 2:\n",
    "#             return len(tree)\n",
    "#         p1 = 0\n",
    "#         p2 = 0\n",
    "#         n1 = 0\n",
    "#         n2 = 0\n",
    "#         t1 = tree[p1]\n",
    "#         t2 = tree[p1]\n",
    "#         max_cur = 0\n",
    "            \n",
    "#         while p2 < len(tree):\n",
    "#             if tree[p2] == t1:\n",
    "#                 n1 += 1\n",
    "#             elif tree[p2] == t2:\n",
    "#                 n2 += 1\n",
    "#             else:\n",
    "#                 if max_cur < n1 + n2:\n",
    "#                     max_cur = n1 + n2\n",
    "#                 while n1 and n2:\n",
    "#                     if tree[p1] == t1:\n",
    "#                         n1 -= 1\n",
    "#                     elif tree[p1] == t2:\n",
    "#                         n2 -= 1\n",
    "#                     p1 += 1\n",
    "#                 if not n1:\n",
    "#                     t1 = tree[p2]\n",
    "#                     n1 = 1\n",
    "#                 if not n2:\n",
    "#                     t2 = tree[p2]\n",
    "#                     n2 = 1\n",
    "#             p2 += 1\n",
    "#         return max(max_cur, p2-p1)\n",
    "        # geiguile !!!\n",
    "        res = cur = count_b = a = b = 0\n",
    "        for c in tree:\n",
    "            cur = cur + 1 if c in (a, b) else count_b + 1\n",
    "            count_b = count_b + 1 if c == b else 1\n",
    "            if b != c: a, b = b, c\n",
    "            res = max(res, cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree):\n",
    "        \"\"\"\n",
    "        :type tree: List[int]\n",
    "        :rtype: int\n",
    "        totalFruit()BruteForce\n",
    "        1. repeat step1 & step2\n",
    "        2. iter all trees\n",
    "        3. return the max tree\n",
    "        \"\"\"\n",
    "        max_collection, N = 0, len(tree)\n",
    "        if len(set(tree)) <= 2:\n",
    "            return N\n",
    "        for q in range(N):\n",
    "            p, stack , type = q, set(), 0\n",
    "            # step2:\n",
    "            while p < N:\n",
    "                # step1:\n",
    "                if tree[p] not in stack:\n",
    "                    if type <= 1:\n",
    "                        stack.add(tree[p])\n",
    "                        type += 1\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    stack.add(tree[p])\n",
    "\n",
    "                p += 1\n",
    "               # print(stack)\n",
    "            max_collection = max(max_collection, p - q)\n",
    "        return max_collection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree):\n",
    "        \"\"\"\n",
    "        :type tree: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # if len(tree)<3:\n",
    "        #     return len(tree)\n",
    "        # for l in range(3,len(tree)+1):\n",
    "        #     record = {}\n",
    "        #     cnt = 0\n",
    "        #     for i in range(l):\n",
    "        #         if tree[i] in record:\n",
    "        #             record[tree[i]] += 1\n",
    "        #         else:\n",
    "        #             record[tree[i]] = 1\n",
    "        #             cnt += 1\n",
    "        #     # print()\n",
    "        #     if cnt<=2:\n",
    "        #         if l==len(tree):\n",
    "        #             return l\n",
    "        #         else:\n",
    "        #             continue\n",
    "        #     i,j = 0,l\n",
    "        #     found = 0\n",
    "        #     while j<len(tree):\n",
    "        #         # print(record,i,j)\n",
    "        #         if tree[i]!=tree[j]:\n",
    "        #             record[tree[i]]-=1\n",
    "        #             if not record[tree[i]]:\n",
    "        #                 del record[tree[i]]\n",
    "        #                 cnt-=1\n",
    "        #             if tree[j] in record:\n",
    "        #                 record[tree[j]]+=1\n",
    "        #             else:\n",
    "        #                 record[tree[j]]=1\n",
    "        #                 cnt+=1\n",
    "        #             if cnt<=2:\n",
    "        #                 found = 1\n",
    "        #                 break\n",
    "        #                 # continue\n",
    "        #         i+=1\n",
    "        #         j+=1\n",
    "        #     if found:\n",
    "        #         continue\n",
    "        #     return l-1\n",
    "        if len(tree)<3:\n",
    "            return len(tree)\n",
    "        i,j = 0,2\n",
    "        record = set(tree[:2])\n",
    "        res = 0\n",
    "        while j<len(tree):\n",
    "            # print(record,i,j,res)\n",
    "            if tree[j] in record:\n",
    "                j+=1\n",
    "            elif len(record)<2:\n",
    "                record.add(tree[j])\n",
    "                j+=1\n",
    "            else:\n",
    "                res = max(j-i,res)\n",
    "                # i,j = j-1,j\n",
    "                i = j-1\n",
    "                while i>=0 and tree[i]==tree[i-1]:\n",
    "                    i-=1\n",
    "                \n",
    "                record = set([tree[i],tree[j]])\n",
    "        print(\"====\",record,i,j,res)\n",
    "        return max(res,j-i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree):\n",
    "        \"\"\"\n",
    "        :type tree: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxc = 0\n",
    "        bask = []\n",
    "        count = 0\n",
    "        for f in range(len(tree)):\n",
    "            if tree[f] in bask:\n",
    "                count += 1\n",
    "            else:\n",
    "                if len(bask) < 2:\n",
    "                    count += 1\n",
    "                    bask.append(tree[f])\n",
    "                else:\n",
    "                    maxc = max(maxc, count)\n",
    "                    count = 1\n",
    "                    i = 1\n",
    "                    while f-i >= 0 and tree[f-i] == tree[f-1]:\n",
    "                        count += 1\n",
    "                        i += 1\n",
    "                    bask = [tree[f-1], tree[f]]\n",
    "        maxc = max(maxc, count)\n",
    "        return maxc\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree):\n",
    "        \"\"\"\n",
    "        :type tree: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 翻译为数学语言，给定一个数组，计算其含有两个元素的最长子数组\n",
    "        n = len(tree)\n",
    "        if n <= 2:\n",
    "            return n\n",
    "        from collections import defaultdict\n",
    "                     \n",
    "        cnt = 0\n",
    "        d = defaultdict(int)\n",
    "        out = []\n",
    "        for index, each in enumerate(tree):\n",
    "            if len(d) < 2:\n",
    "                cnt = cnt + 1                \n",
    "            else:\n",
    "                if each in d:\n",
    "                    cnt = cnt + 1\n",
    "                else:\n",
    "                    pre_index = min(d.values())                    \n",
    "                    \n",
    "                    \n",
    "                    for k, v in d.items():\n",
    "                        if v == pre_index:\n",
    "                            del d[k]\n",
    "                            break\n",
    "                    cnt = index - pre_index\n",
    "            d[each] = index\n",
    "            out.append(cnt)\n",
    "        return max(out)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree: 'List[int]') -> 'int':\n",
    "        if len(tree) == 0: return 0\n",
    "        start = new_start = 0\n",
    "        type_a , type_b = tree[0], -1\n",
    "        res = 1\n",
    "        for i in range(1, len(tree)):\n",
    "            if i == 0: continue\n",
    "            if type_b == -1 and type_a != tree[i]:\n",
    "                type_b = tree[i]\n",
    "            elif tree[i] != type_a and tree[i] != type_b:\n",
    "                start = new_start\n",
    "                type_a = tree[i-1]\n",
    "                type_b = tree[i]\n",
    "                \n",
    "            res = max(res, i-start+1)\n",
    "            \n",
    "            if tree[i] != tree[i-1]: new_start = i\n",
    "                \n",
    "        return res \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree: List[int]) -> int:\n",
    "        found = {tree[0]}\n",
    "        start = 0\n",
    "        ans = 0\n",
    "        count = 1\n",
    "        for i in range(1, len(tree)):\n",
    "            if tree[i] in found:\n",
    "                count += 1\n",
    "            elif len(found) < 2:\n",
    "                count += 1\n",
    "                found.add(tree[i])\n",
    "            else:\n",
    "                ans = max(ans, count)\n",
    "                count = i - start + 1\n",
    "                found = {tree[i], tree[i-1]}\n",
    "            if tree[i] != tree[i-1]:\n",
    "                start = i\n",
    "        return max(ans, count)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree: List[int]) -> int:\n",
    "        left=0\n",
    "        leftV=tree[0]\n",
    "        rightV=-1\n",
    "        res=0\n",
    "        last=0\n",
    "\n",
    "        for i in range(1,len(tree)):\n",
    "            \n",
    "            if tree[i]==leftV or tree[i]==rightV:\n",
    "                if tree[i]!=tree[last]:\n",
    "                    last=i\n",
    "                continue\n",
    "            else:\n",
    "                if rightV==-1: \n",
    "                    rightV=tree[i]\n",
    "                    last=i\n",
    "                else:\n",
    "                    res=max(res,i-left)\n",
    "                    left=last\n",
    "                    leftV=tree[last]\n",
    "                    rightV=tree[i]\n",
    "                    last=i\n",
    "        return max(res,len(tree)-left)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree: List[int]) -> int:\n",
    "        tmp = [tree.pop(0)]\n",
    "        settmp = set(tmp)\n",
    "        ans = 1\n",
    "        while(tree):\n",
    "            tmp2 = tree.pop(0)\n",
    "            if len(settmp) < 2:\n",
    "                settmp = settmp | {tmp2}\n",
    "                tmp.append(tmp2)\n",
    "                ans = max(ans, len(tmp))\n",
    "            elif tmp2 in settmp:\n",
    "                tmp.append(tmp2)\n",
    "                ans = max(ans, len(tmp))\n",
    "            else:\n",
    "                tmp.append(tmp2)\n",
    "                while(len(set(tmp)) == 3):\n",
    "                    tmp.pop(0)\n",
    "                settmp = set(tmp)\n",
    "        return ans\n",
    "                \n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree: List[int]) -> int:\n",
    "        basket = set()\n",
    "        num = 0\n",
    "        max_num = 0\n",
    "        i = 0\n",
    "        cur_index = 0\n",
    "        while i < len(tree):\n",
    "            for j in range(i, len(tree)):\n",
    "                if tree[j] in basket:\n",
    "                    num += 1\n",
    "                else:\n",
    "                    if len(basket) == 2:\n",
    "                        max_num = max(max_num, num)\n",
    "                        num = 0\n",
    "                        basket.clear()\n",
    "                        break\n",
    "                    else:\n",
    "                        if len(basket) == 1:\n",
    "                            cur_index = j\n",
    "                        basket.add(tree[j])\n",
    "                        num += 1\n",
    "            if len(basket) != 0:\n",
    "                break\n",
    "            i = cur_index\n",
    "        max_num = max(max_num, num)\n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def totalFruit(self, tree: List[int]) -> int:\n",
    "        i=0\n",
    "        bucket=collections.Counter()\n",
    "        maxlen=0\n",
    "        for j in range(len(tree)):\n",
    "            bucket[tree[j]]+=1\n",
    "            while(len(bucket)>2):\n",
    "                bucket[tree[i]]-=1\n",
    "                if(bucket[tree[i]]==0):\n",
    "                    del bucket[tree[i]]\n",
    "                i+=1\n",
    "            maxlen=max(maxlen,j-i+1)\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree: List[int]) -> int:\n",
    "        start = 0\n",
    "        res = 0\n",
    "        dic = collections.Counter()\n",
    "        for i in range(len(tree)):\n",
    "            # if tree[i] in dic:\n",
    "            #     dic[tree[i]] += 1\n",
    "            # else:\n",
    "            #     dic[tree[i]] = 1\n",
    "            dic[tree[i]] += 1\n",
    "            while len(dic)>=3:\n",
    "                dic[tree[start]] -= 1\n",
    "                if dic[tree[start]] == 0:\n",
    "                    del dic[tree[start]]\n",
    "                start += 1\n",
    "            res = max(res,i-start+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, tree: List[int]) -> int:\n",
    "        windowStart = 0\n",
    "        count = Counter()\n",
    "        totalNum = 0\n",
    "        for windowEnd in range(len(tree)):\n",
    "            count[tree[windowEnd]] += 1\n",
    "            while len(count) >= 3:\n",
    "                count[tree[windowStart]] -= 1\n",
    "                if count[tree[windowStart]] == 0:\n",
    "                    del count[tree[windowStart]]\n",
    "                windowStart += 1\n",
    "            totalNum = max(totalNum, windowEnd - windowStart + 1)\n",
    "        return totalNum\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        if len(fruits) <= 2:\n",
    "            return len(fruits)\n",
    "        index = 0\n",
    "        maxim = 0\n",
    "        pre = None\n",
    "        while index < len(fruits):\n",
    "            baskets = []\n",
    "            result = 0\n",
    "            if fruits[index]==pre:\n",
    "                index = index + 1\n",
    "                continue\n",
    "            else:\n",
    "                pre = fruits[index]\n",
    "                count = index\n",
    "                while count<len(fruits):\n",
    "                    i = fruits[count]\n",
    "                    if i in baskets:\n",
    "                        result=result+1\n",
    "                    elif len(baskets)==2:\n",
    "                        break\n",
    "                    elif len(baskets)<2:\n",
    "                        result=result+1\n",
    "                        baskets.append(i)\n",
    "                    count=count+1\n",
    "                if result>maxim:\n",
    "                    maxim = result\n",
    "                if count == len(fruits):\n",
    "                    print('hei')\n",
    "                    break\n",
    "            index=index+1\n",
    "        return maxim"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        count = defaultdict(int)\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        for r in range(len(fruits)):\n",
    "            \n",
    "            count[fruits[r]] += 1\n",
    "            while len(count) >= 3:\n",
    "                count[fruits[l]] -= 1\n",
    "                if count[fruits[l]]==0: del count[fruits[l]]\n",
    "                l += 1\n",
    "            ans = max(ans, r - l +1)\n",
    "\n",
    "        return ans\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        res = index = 0\n",
    "        count = collections.Counter()\n",
    "        for i, num in enumerate(fruits):\n",
    "            count[num] += 1\n",
    "            while len(count) >= 3:\n",
    "                count[fruits[index]] -= 1\n",
    "                if count[fruits[index]] == 0:\n",
    "                    del count[fruits[index]]\n",
    "                index += 1\n",
    "            res = max(res, (i-index+1))\n",
    "        return res\n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        ans = i = 0\n",
    "        counter = collections.Counter()\n",
    "        for index , y in enumerate(fruits):\n",
    "            counter[y] += 1\n",
    "            while len(counter) >= 3:\n",
    "                counter[fruits[i]] -= 1\n",
    "                if counter[fruits[i]] == 0:\n",
    "                    del counter[fruits[i]]\n",
    "                i += 1\n",
    "            ans = max(ans,index-i+1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits):\n",
    "        maxnum=0\n",
    "        label=[[-1,-1],[0,fruits[0]]]\n",
    "        i=0\n",
    "        bg=0\n",
    "        while i<len(fruits):\n",
    "            if fruits[i]!=label[1][1]:\n",
    "                \n",
    "                if fruits[i]!=label[0][1]:\n",
    "                    #maxnum.append(i-bg)\n",
    "                    if i-bg>maxnum:\n",
    "                        maxnum=i-bg\n",
    "                    bg=label[1][0]  \n",
    "                    \n",
    "                label[0]=label[1].copy()\n",
    "                label[1][0]=i\n",
    "                label[1][1]=fruits[i]\n",
    "                \n",
    "            i+=1\n",
    "        #maxnum.append(i-bg)\n",
    "        if i-bg>maxnum:\n",
    "            maxnum=i-bg\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        l, r = 0, 0\n",
    "        f_type = 0\n",
    "        dic = {}\n",
    "        res = 0\n",
    "        while r < len(fruits):\n",
    "            if fruits[r] in dic:\n",
    "                dic[fruits[r]] += 1\n",
    "            else:\n",
    "                dic[fruits[r]] = 1\n",
    "                f_type += 1\n",
    "                if f_type > 2:\n",
    "                    while f_type > 2:\n",
    "                        dic[fruits[l]] -= 1\n",
    "                        if dic[fruits[l]] == 0:\n",
    "                            dic.pop(fruits[l])\n",
    "                            f_type -= 1\n",
    "                        l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "            r += 1\n",
    "        return res\n",
    "\n",
    "    # def totalFruit(self, fruits: List[int]) -> int:\n",
    "    #     cnt = Counter()\n",
    "\n",
    "    #     left = ans = 0\n",
    "    #     for right, x in enumerate(fruits):\n",
    "    #         cnt[x] += 1\n",
    "    #         while len(cnt) > 2:\n",
    "    #             cnt[fruits[left]] -= 1\n",
    "    #             if cnt[fruits[left]] == 0:\n",
    "    #                 cnt.pop(fruits[left])\n",
    "    #             left += 1\n",
    "    #         ans = max(ans, right - left + 1)\n",
    "        \n",
    "    #     return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        res = float('-inf')\n",
    "        i, j = 0, 0\n",
    "        dic = {}\n",
    "        n = len(fruits)\n",
    "        for fruit in range(n):\n",
    "            while j <= n-1 and len(dic) <= 2:\n",
    "                k = fruits[j]\n",
    "                dic[k] = 1 if k not in dic else dic[k]+1\n",
    "                j += 1\n",
    "            res = max(res, j-i-1)\n",
    "            while i <= n-1 and len(dic)>2:\n",
    "                k = fruits[i]\n",
    "                dic[k] -= 1\n",
    "                if dic[k] ==0:\n",
    "                    dic.pop(k)\n",
    "                i += 1\n",
    "        res = max(res, j-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        i = sum = 0\n",
    "        cnt = Counter()\n",
    "        for j, x in enumerate(fruits):\n",
    "            cnt[x] += 1\n",
    "            while len(cnt) >2:\n",
    "                cnt[fruits[i]] -= 1\n",
    "                if cnt[fruits[i]] == 0:\n",
    "                    cnt.pop(fruits[i])\n",
    "                i += 1\n",
    "            sum = max(sum,j-i+1)\n",
    "        return sum\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        slow = 0\n",
    "        subNum = 0\n",
    "        maxNum = 0\n",
    "        count = 0\n",
    "        type_array = [0] * (len(fruits))\n",
    "        for fast in range(len(fruits)):\n",
    "            if type_array[fruits[fast]] == 0:\n",
    "                count += 1\n",
    "            type_array[fruits[fast]] += 1\n",
    "            while count > 2:\n",
    "                subNum = fast - slow\n",
    "                maxNum = max(maxNum, subNum)\n",
    "                type_array[fruits[slow]] -= 1\n",
    "                if type_array[fruits[slow]] == 0:\n",
    "                    count -= 1\n",
    "                slow += 1\n",
    "            subNum = fast - slow + 1\n",
    "            maxNum = max(maxNum, subNum)\n",
    "        return maxNum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        left,ans=0,0\n",
    "        mydict=dict()\n",
    "        for index,type in enumerate(fruits):\n",
    "            mydict[type]=mydict.get(type,0)+1\n",
    "            while len(mydict)>2:\n",
    "                mydict[fruits[left]]-=1\n",
    "                if mydict[fruits[left]]<=0:\n",
    "                    del mydict[fruits[left]]\n",
    "                left+=1\n",
    "            ans=max(ans,index-left+1)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        \n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "\n",
    "        for right,x in enumerate(fruits):\n",
    "            cnt[x]+=1\n",
    "            while len(cnt) > 2:\n",
    "                cnt[fruits[left]] -= 1\n",
    "                if cnt[fruits[left]] == 0:\n",
    "                    cnt.pop(fruits[left])\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "class Solution:\r\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        i = j = 0\r\n",
    "        dit = {}\r\n",
    "        while j <= len(fruits) - 1:\r\n",
    "            while j<= len(fruits) - 1 and len(dit)<=2:\r\n",
    "                v = fruits[j]\r\n",
    "                dit[v] = 1 if v not in dit else dit[v]+1\r\n",
    "                j += 1\r\n",
    "            res = max(res, j-i-1)\r\n",
    "            while i < len(fruits)-1 and len(dit)>2:\r\n",
    "                u = fruits[i]\r\n",
    "                dit[u] -= 1\r\n",
    "                if dit[u] == 0:\r\n",
    "                    dit.pop(u)\r\n",
    "                i += 1\r\n",
    "        res = max(res, j-i)\r\n",
    "        return res\r\n",
    "               \r\n",
    "        \r\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        def remove_from_dict(fruit, f_dict):\n",
    "            if f_dict.get(fruit, 0) > 1:\n",
    "                f_dict[fruit] -= 1\n",
    "            else:\n",
    "                f_dict.pop(fruit)\n",
    "        def add_to_dict(fruit, f_dict):\n",
    "            if fruit in f_dict:\n",
    "                f_dict[fruit] += 1\n",
    "            else:\n",
    "                f_dict[fruit] = 1\n",
    "        ## 选连续的，两种数字和最大\n",
    "        fruit_dict = {}\n",
    "        right = 0\n",
    "        left = 0\n",
    "        L = len(fruits)\n",
    "        max_num = 0\n",
    "        ## 缩到只有两种水果\n",
    "\n",
    "        ## 什么时候把right加进去有讲究\n",
    "        ## 什么时候缩有讲究\n",
    "        ## 什么时候取最大/最小值有讲究\n",
    "        while right < L:\n",
    "            add_to_dict(fruits[right], fruit_dict)\n",
    "            right += 1\n",
    "            while len(fruit_dict.keys()) > 2:\n",
    "                remove_from_dict(fruits[left], fruit_dict)\n",
    "                left += 1\n",
    "            print(fruit_dict)\n",
    "            max_num = max(sum(fruit_dict.values()), max_num)\n",
    "        return max_num\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        mp = defaultdict(int)\n",
    "        left = 0\n",
    "        n = len(fruits)\n",
    "        res = 0\n",
    "        for right in range(n):\n",
    "            mp[fruits[right]] += 1\n",
    "            while len(mp)>2:\n",
    "                mp[fruits[left]] -= 1\n",
    "                if mp[fruits[left]] == 0:\n",
    "                    mp.pop(fruits[left])\n",
    "                left += 1\n",
    "            print(left)\n",
    "            res = max(res,right-left+1)\n",
    "        return res\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        mp = defaultdict(int)\n",
    "        left = 0\n",
    "        n = len(fruits)\n",
    "        res = 0\n",
    "        for right in range(n):\n",
    "            mp[fruits[right]] += 1\n",
    "            while len(mp)>2:\n",
    "                mp[fruits[left]] -= 1\n",
    "                if mp[fruits[left]] == 0:\n",
    "                    del mp[fruits[left]]\n",
    "                left += 1\n",
    "            print(left)\n",
    "            res = max(res,right-left+1)\n",
    "        return res\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalFruit(self, fruits: List[int]) -> int:\n",
    "        curren_fruit = fruits[0],\n",
    "        last = cnt = ans = 1\n",
    "        for l, r in pairwise(fruits):\n",
    "            if r not in curren_fruit:\n",
    "                cnt = last\n",
    "                curren_fruit = l, r\n",
    "            cnt += 1\n",
    "            if cnt > ans:\n",
    "                ans = cnt\n",
    "            last = last + 1 if l == r else 1\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
